# Author    :Dun_Hz
# Time      :2024/3/15 9:33
# 用递归求迷宫问题

def mark(maze, pos):        #给迷宫maze的位置pos标“2”表示”来过“
    maze[pos[0]][pos[1]] = 2
def passable(maze, pos):        #检查迷宫maze的位置pos是否可通行
    return maze[pos[0]][pos[1]] == 0        # 如果为0，说明可能性，返回True
def find_path(maze, pos, end):
    mark(maze,pos)
    if pos == end:
        print(pos, end=' ')     #出口达到，输出出口位置
        path.append(pos)
        return True
    for i in range(4):      # 检查4个方向是否可通行
        nextp = pos[0] +dirs[i][0], pos[1]+dirs[i][1]
        # 考虑下一个可能的方向
        if passable(maze, nextp):
            if find_path(maze,nextp,end):       # 调用自身
                # 如果从nextp可到出口，输出这个位置，结束
                print(pos, end=" ")
                path.append(pos)
                return True
    return False
def see_path(maze,path):            #使找到的路径可视化
    for i,p in enumerate(path):
        if i == 0:
            maze[p[0]][p[1]] = "E"
        elif i == len(path)-1:
            maze[p[0]][p[1]] = "S"
        else:
            maze[p[0]][p[1]] = 3
    print("\n")
    for row in maze:
        for col in row:
            if col == 3:
                print('\033[0;31m' + '*' +' '+'\033[0m', end = '')
            elif col == 'S' or col =='E':
                print('\033[0;34m' + col + ' ' + '\033[0m', end='')
            elif col == 2:
                print('\033[0;32m' + '#' + ' ' + '\033[0m', end='')
            elif col == 1:
                print('\033[0;;40m' + ' ' + ' ' + '\033[0m', end='')
            else:
                print("  ",end = '')
        print()
if __name__ == '__main__':
    maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
            [1, 0, 0, 1, 0, 1, 0, 1, 1, 1],
            [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 1, 1, 1, 0, 1],
            [1, 1, 0, 1, 0, 1, 0, 1, 1, 1],
            [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
            [1, 1, 1, 0, 1, 0, 1, 0, 1, 1],
            [1, 1, 1, 0, 0, 0, 1, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 当前位置四个方向的偏量
    path = []  # 最终的路径
    start=(1,1)
    end = (7,8 )
    find_path(maze,start,end)
    see_path(maze,path)
